Given a grid consisting of '0's(Water) and '1's(Land). Find the number of islands.
Note: An island is surrounded by water and is formed by connecting adjacent lands horizontally or
vertically or diagonally i.e., in all 8 directions.
Example 1:
Input:
grid = {{0,1},{1,0},{1,1},{1,0}}
Output:
1
Explanation:
The grid is-
0 1
1 0
1 1
1 0
All lands are connected.
Example 2:
Input:
grid = {{0,1,1,1,0,0,0},{0,0,1,1,0,1,0}}
Output:
2
Expanation:
The grid is-
0 1 1 1 0 0 0
0 0 1 1 0 1 0
Code
void dfs(vector<vector<char>>& grid,int i,int j)
{
if(i>=0&&j>=0&&i<grid.size()&&j<grid[0].size()&&grid[i][j]=='1')
{
grid[i][j]=0;
dfs(grid,i+1,j);
dfs(grid,i,j-1);
dfs(grid,i,j+1);
dfs(grid,i+1,j+1);
dfs(grid,i+1,j-1);
dfs(grid,i-1,j+1);
dfs(grid,i-1,j-1);
dfs(grid,i-1,j);
dfs(grid,i,j);
}
return ;
}
int numIslands(vector<vector>& grid)
{
int i,j;
int count=0;
for(i=0;i<grid.size();i++)
{
for(j=0;j<grid[0].size();j++)
{
if(grid[i][j]=='1')
{
dfs(grid,i,j);
count++;
}
}
}
return count;
}